/*****************************************************************************
 *  ENTROPY - emerging network to reduce orwellian potency yield
 *
 *  Copyright (C) 2002 Juergen Buchmueller <pullmoll@stop1984.com>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software Foundation,
 *  Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 *
 *	$Id: memalloc.c,v 1.5 2006/02/18 20:30:22 pullmoll Exp $
 *****************************************************************************/
#include "osd.h"
#include "config.h"
#include "memalloc.h"
#include "logger.h"

#if	MEM_ALLOC_IMPL

#if	MEM_DEBUG
#undef	NDEBUG
#include "tools.h"
#define	assert(e) if(!(e)){LOGS(L_MEM,L_ERROR,("assert:"#e "\n"));}
#else
#define	NDEBUG
#define	assert(e)
#endif

typedef	double align_t;

typedef union mem_node_u {
	struct {
		size_t rsize;	/* real size */
		size_t usize;	/* user size */
#if	MEM_DEBUG
		char *file;
		uint32_t line;
#endif
		union mem_node_u *next;
	} x;
	align_t align;
}	mem_node_t;

typedef enum list_e {
	AVAIL,
	ALLOC
}	list_t;

#undef	PAGESIZE
#define	PAGESIZE	1024

#define	LOCK()	(0)
#define	UNLOCK()

#undef	OBLITERATE
#undef	DISPLAY
#undef	BOUNDS
#undef	ZERO_ERROR
#undef	NULL_ERROR
#undef	INVALID_ERROR
#define	BESTFIT

#undef	FIT
#ifdef	BESTFIT
#define	FIT(x)	bestfit(x FILE_LINE_PARMS)
#else	/* BESTFIT */
#define	FIT(x)	firstfit(x FILE_LINE_PARMS)
#endif	/* !BESTFIT */

#undef	PATTERN
#define	PATTERN(p)	((char)((uint32_t)(p) & 0xff))
#undef	MIN
#define	MIN(x,y)	((x) < (y) ? (x) : (y))
#undef	MAX
#define	MAX(x,y)	((x) > (y) ? (x) : (y))
#undef	ALIGN
#define	ALIGN(p)	(((p) + (sizeof(align_t) - 1)) & ~(sizeof(align_t) - 1))

#undef	ADDR
#undef	AFTER
#undef	OVERHEAD

#ifdef	BOUNDS
#define	ADDR(n)		((caddr_t)(n) + sizeof(mem_node_t) + sizeof(align_t))
#define	AFTER(n)	(ADDR(n) + (n)->x.rsize + sizeof(align_t))
#define	OVERHEAD	(sizeof(mem_node_t) + (2 * sizeof(align_t)))
#else
#define	ADDR(n)		((caddr_t)(n) + sizeof(mem_node_t))
#define	AFTER(n)	(ADDR(n) + (n)->x.rsize)
#define	OVERHEAD	(sizeof(mem_node_t))
#endif	/* BOUNDS */

#undef	STATUS
#ifdef	DISPLAY
#define	STATUS(s) \
	LOGS(L_MEM,L_MINOR,("%8d %05u/%04u %4.1f%% (%7s) <%8s:%-5d>\n", \
		g_mem->total, \
		(unsigned)g_mem->alloc_len, \
		(unsigned)g_mem->avail_len, \
		(g_mem->avail_len + g_mem->alloc_len) ? \
			g_mem->avail_len*99.9 / (g_mem->avail_len+g_mem->alloc_len):0.0, \
		(s), \
		((file) ? (file) : "unknown"), \
		((line) ? (line) : 0)))
#else
#define	STATUS(s)
#endif

#undef	MINNODE
#define	MINNODE	(64 * sizeof(align_t))

#undef	ADJACENT
#define	ADJACENT(n1,n2) \
		((caddr_t)(n1) + OVERHEAD + (n1)->x.rsize == (caddr_t)(n2))

mem_pool_t *g_mem = NULL;

/* put a breakpoint here for debugging */
static void debug() {
	g_mem->total = g_mem->total;
}

#if	MEM_DEBUG
static char *at_file_line(char *file, uint32_t line)
{
	static char buff[4][80];
	static int which = 0;

	which = (which + 1) % 4;
	if (NULL == file) {
		buff[which][0] = '\0';
	} else {
		pm_snprintf(buff[which], sizeof(buff[which]), " at %s:%d", file, line);
	}
	return buff[which];
}
#endif

#if	MEM_DEBUG
static void pnode(mem_node_t *n)
{
	FUN("pnode");
	LOGS(L_MEM,L_ERROR,
		("%p: rsize=%#x, usize=%#x, addr=%p, next=%p (%s:%u)\n",
		n, (unsigned)n->x.rsize, (unsigned)n->x.usize,
		ADDR(n), n->x.next,
		(char *)((NULL != n->x.file) ? n->x.file : "unknown"), n->x.line));
}

static void plist(mem_node_t *head)
{
	mem_node_t *c;
	FUN("plist");

	LOGS(L_MEM,L_ERROR,("=== list starts at %p ===\n", head));
	c = head;
	while (NULL != c) {
		pnode(c);
		c = c->x.next;
	}
}

static int any_pool(mem_node_t *prev, mem_node_t *node)
{
	uint32_t i;
	uint8_t *addr = (uint8_t *)node;
	FUN("any_pool");

	for (i = 0; i < g_mem->pool_cnt; i++) {
		if (addr >= g_mem->pool[i] && addr < &g_mem->pool[i][g_mem->brk[i]])
			return 1;
	}
	LOGS(L_MEM,L_ERROR,("node %p (prev %p) is not in any pool\n",
		addr, prev));
	plist(g_mem->allocated);
	return 0;
}
#endif

#ifndef	NDEBUG
static uint32_t alloc_len(void)
{
	uint32_t i = 0;
	mem_node_t *curr = (mem_node_t *)g_mem->allocated;
	mem_node_t *prev = NULL;
	FUN("alloc_len");
	while (NULL != curr) {
		i++;
		assert(any_pool(prev, curr));
		prev = curr;
		curr = curr->x.next;
	}
	return i;
}

static uint32_t avail_len(void)
{
	uint32_t i = 0;
	mem_node_t *curr = (mem_node_t *)g_mem->available;
	mem_node_t *prev = NULL;
	FUN("avail_len");
	while (NULL != curr) {
		i++;
		assert(any_pool(prev, curr));
		prev = curr;
		curr = curr->x.next;
	}
	return i;
}
#endif

static void delete(list_t l, mem_node_t *node)
{
	mem_node_t *curr, *prev, **head;
	FUN("delete");

	assert(ALLOC == l || AVAIL == l);
	assert(NULL != node);
	if (l == ALLOC) {
		head = (mem_node_t **)&g_mem->allocated;
		assert(g_mem->alloc_len == alloc_len());
	} else {
		head = (mem_node_t **)&g_mem->available;
		assert(g_mem->avail_len == avail_len());
	}
	assert(NULL != *head);

	curr = prev = *head;
	while (NULL != curr && ADDR(curr) > ADDR(node)) {
		prev = curr;
		curr = curr->x.next;
	}
	assert(NULL != curr);

	if (ALLOC == l) {
		g_mem->alloc_len -= 1;
	} else {
		g_mem->avail_len -= 1;
	}

	if (curr == prev) {
		*head = curr->x.next;
	} else {
		prev->x.next = curr->x.next;
	}
}	/* delete */


static void insert(list_t l, mem_node_t *node)
{
	mem_node_t *curr, *prev, **head;
	FUN("insert");

	assert(ALLOC == l || AVAIL == l);
	assert(NULL != node);
	if (l == ALLOC) {
		head = (mem_node_t **)&g_mem->allocated;
		assert(g_mem->alloc_len == alloc_len());
	} else {
		head = (mem_node_t **)&g_mem->available;
		assert(g_mem->avail_len == avail_len());
	}

	curr = prev = *head;
	while (NULL != curr && ADDR(curr) > ADDR(node)) {
		prev = curr;
		curr = curr->x.next;
	}

	assert(NULL == curr || ADDR(curr) != ADDR(node));

	if (AVAIL == l && NULL != *head && NULL != curr && ADJACENT(curr,node)) {
		curr->x.rsize += OVERHEAD + node->x.rsize;
		if (ADJACENT(curr,prev)) {
			delete(AVAIL, prev);
			curr->x.rsize += OVERHEAD + prev->x.rsize;
		}
	} else {
		if (ALLOC == l) {
			g_mem->alloc_len += 1;
		} else {
			g_mem->avail_len += 1;
		}
		node->x.next = curr;
		if (curr == prev) {
			*head = node;
		} else {
			prev->x.next = node;
			if (AVAIL == l && NULL != *head && ADJACENT(node,prev)) {
				delete(AVAIL, prev);
				node->x.rsize += OVERHEAD + prev->x.rsize;
			}
		}
	}
}	/* insert */

#ifdef	BOUNDS
static void fillbounds(mem_node_t *node)
{
	char *start;
	char pattern = PATTERN(node);
	int length, i;

	start = (char *)node + sizeof(mem_node_t);
	length = sizeof(align_t);
	for (i = 0; i < length; i++) {
		start[i] = pattern;
	}

	start = (char *)node + sizeof(mem_node_t) + sizeof(align_t) + node->x.usize;
	length = node->x.rsize - node->x.usize + sizeof(align_t);
	for (i = 0; i < length; i++) {
		start[i] = pattern;
	}
}	/* fillbounds */

static void checkbounds(mem_node_t *node, char *func)
{
	int i, start, end, bad = 0;
	uint8_t current, pattern = PATTERN(node);
	FUN("checkbounds");

#define	CHECK(i) \
		current = ((uint8_t *)ADDR(node))[i]; \
		if (current != pattern) { \
			LOGS(L_MEM,L_ERROR, \
				("%s: found '\\%03o' instead of '\\%03o' at 0x%x[%d]\n", \
				func, current, pattern, (unsigned)ADDR(node), (i))); \
			pnode(node); \
			debug(); \
			bad++; \
		}

	start = -sizeof(align_t);
	end = 0;
	for (i = start; i < end; i++) {
		CHECK(i);
	}

	start = node->x.usize;
	end = node->x.rsize + sizeof(align_t);
	for (i = start; i < end; i++) {
		CHECK(i);
	}
	if (bad > 0)
		plist(g_mem->allocated);
}	/* checkbounds */

static void lbounds(mem_node_t *head)
{
	mem_node_t *curr = head;
	while (NULL != curr) {
		checkbounds(curr, "lbounds");
		curr = curr->x.next;
	}
}	/* lbounds */
#else
#define	fillbounds(n)
#define	checkbounds(n,f)
#define	lbounds(h)
#endif

static mem_node_t *find(mem_node_t *head, caddr_t ptr)
{
	mem_node_t *curr = head;
	mem_node_t *prev = NULL;
	FUN("find");

	while (NULL != curr && ADDR(curr) != ptr) {
		assert(any_pool(prev, curr));
		prev = curr;
		curr = curr->x.next;
	}

	if (NULL == curr || ADDR(curr) != ptr) {
		return NULL;
	}

	return curr;
}	/* find */

static mem_node_t *expand(size_t size FILE_LINE_ARGS)
{
	mem_node_t *node = NULL;
	size_t i, big;
	FUN("expand");

	lbounds(g_mem->allocated);
	big = MAX((8 * PAGESIZE), (((size + OVERHEAD) / PAGESIZE) + 1) * PAGESIZE);
	assert(big >= size + OVERHEAD);

	/* find a pool where 'big' fits into */
	for (i = 0; i < g_mem->pool_cnt; i++) {
		if (g_mem->brk[i] + big <= g_mem->max[i]) {
			node = (mem_node_t *)&g_mem->pool[i][g_mem->brk[i]];
			g_mem->brk[i] = g_mem->brk[i] + big;
			break;
		}
	}
	if (i == g_mem->pool_cnt && i < MEM_POOLSEGS) {
		size_t max;
		max = g_mem->max[i-1] * 2;
		while (max < big)
			max <<= 1;
		g_mem->max[i] = max;
		g_mem->pool[i] = malloc(max);
		if (NULL == g_mem->pool[i]) {
			LOGS(L_MEM,L_ERROR,("expand: allocating 0x%x failed\n",
				(unsigned)max));
		} else {
			LOGS(L_MEM,L_DEBUG,("expand: allocated pool %d, size 0x%x @ %p\n",
				(int)i, (unsigned)max, g_mem->pool[i]));
			node = (mem_node_t *)g_mem->pool[i];
			g_mem->brk[i] = g_mem->brk[i] + big;
			g_mem->pool_cnt += 1;
		}
	}

	/* we're lost if no memory pool was found */
	if (i == g_mem->pool_cnt) {
		LOGS(L_MEM,L_ERROR,("expand: setting break +0x%x failed\n",
			(unsigned)big));
		for (i = 0; i < g_mem->pool_cnt; i++) {
			LOGS(L_MEM,L_ERROR,("pool[%d] %#llx/%#llx\n",
				(int)i, (uint64_t)g_mem->brk[i], (uint64_t)g_mem->max[i]));
		}
		die(1,("Out of memory"));
		return NULL;
	}

	node->x.rsize = big - OVERHEAD;
	node->x.next = NULL;
#if	MEM_DEBUG
	node->x.file = file;
	node->x.line = line;
#endif

	return node;
}	/* expand */

#ifndef	BESTFIT
static mem_node_t *firstfit(size_t size FILE_LINE_ARGS)
{
	mem_node_t *curr;
	size_t aligned = ALIGN(size);
	FUN("firstfit");

#if	MEM_DEBUG
	(void)file;
	(void)line;
#endif

#ifdef	ZERO_ERROR
	assert(0 != size);
#endif	/* ZERO_ERROR */

	curr = g_mem->available;
	while (NULL != curr && curr->x.rsize < aligned) {
		curr = curr->x.next;
	}

	if (NULL == curr) {
		if (NULL == (curr = expand(aligned FILE_LINE_PARMS))) {
			return NULL;
		}
	} else {
		assert(NULL == find(g_mem->allocated, ADDR(curr)));
		assert(curr == find(g_mem->available, ADDR(curr)));

		delete(AVAIL, curr);
	}

	assert(NULL == find(g_mem->allocated, ADDR(curr)));
	assert(NULL == find(g_mem->available, ADDR(curr)));

	if (curr->x.rsize >= aligned + OVERHEAD + MINNODE) {
		mem_node_t *node;
		size_t leftover;

		leftover = curr->x.rsize - aligned - OVERHEAD;
		curr->x.rsize = aligned;

		node = (mem_node_t *)AFTER(curr);
		node->x.rsize = leftover;

		assert(NULL == find(g_mem->allocated, ADDR(node)));
		assert(NULL == find(g_mem->available, ADDR(node)));

		insert(AVAIL, node);

		assert(NULL == find(g_mem->allocated, ADDR(node)));
		assert(node == find(g_mem->available, ADDR(node)));
	}

	curr->x.usize = size;

	fillbounds(curr);

	insert(ALLOC, curr);

	assert(curr == find(g_mem->allocated, ADDR(curr)));
	assert(NULL == find(g_mem->available, ADDR(curr)));

	return curr;
}	/* firstfit */

#else	/* BESTFIT */

static mem_node_t *bestfit(size_t size FILE_LINE_ARGS)
{
	mem_node_t *curr, *best;
	size_t aligned = ALIGN(size);
	size_t over, bestover = (size_t)0x7fffffff;
	FUN("bestfit");

#if	MEM_DEBUG
	(void)file;
	(void)line;
#endif

#ifdef	ZERO_ERROR
	assert(0 != size);
#endif	/* ZERO_ERROR */

	best = NULL;
	curr = g_mem->available;
	while (NULL != curr) {
		if (curr->x.rsize >= size) {
			over = curr->x.rsize - size;
			if (over < bestover || curr == g_mem->available) {
				bestover = over;
				best = curr;
			}
		}
		curr = curr->x.next;
	}

	if (NULL == best) {
		if (NULL == (best = expand(aligned FILE_LINE_PARMS))) {
			return NULL;
		}
	} else {
		assert(NULL == find(g_mem->allocated, ADDR(best)));
		assert(best == find(g_mem->available, ADDR(best)));

		delete(AVAIL, best);
	}

	assert(NULL == find(g_mem->allocated, ADDR(best)));
	assert(NULL == find(g_mem->available, ADDR(best)));

	if (best->x.rsize >= aligned + OVERHEAD + MINNODE) {
		mem_node_t *node;
		size_t leftover;

		leftover = best->x.rsize - aligned - OVERHEAD;
		best->x.rsize = aligned;

		node = (mem_node_t *)AFTER(best);
		node->x.rsize = leftover;

		assert(NULL == find(g_mem->allocated, ADDR(node)));
		assert(NULL == find(g_mem->available, ADDR(node)));

		insert(AVAIL, node);

		assert(NULL == find(g_mem->allocated, ADDR(node)));
		assert(node == find(g_mem->available, ADDR(node)));
	}

	best->x.usize = size;

	fillbounds(best);

	insert(ALLOC, best);

	assert(best == find(g_mem->allocated, ADDR(best)));
	assert(NULL == find(g_mem->available, ADDR(best)));

	return best;
}

#endif

/* ------------------------------------------------------- */

/* ARGUSED */
caddr_t mem_malloc(size_t size FILE_LINE_ARGS)
{
	mem_node_t *store;
	FUN("mem_malloc");

	if (NULL == g_mem) mem_pool();
	LOGS(L_MEM,L_DEBUGX,("mem_malloc(%d)%s\n",
		(int)size, AT_FILE_LINE));
	if (0 != LOCK()) {
		LOGS(L_MEM,L_ERROR,("lock failed%s\n",
			AT_FILE_LINE));
		return NULL;
	}
	if (0 == size) {
		LOGS(L_MEM,L_ERROR,("malloc: attempt to allocate 0 bytes%s\n",
			AT_FILE_LINE));
#ifdef	ZERO_ERROR
#if	MEM_DEBUG
		if (NULL != file)
			debug();
#endif
		UNLOCK();
		return NULL;
#endif	/* ZERO_ERROR */
	}

	store = FIT(size);

	if (NULL == store) {
		LOGS(L_MEM,L_ERROR,("malloc: unable to allocate %d bytes%s\n",
			(int)size, AT_FILE_LINE));
		debug();
		UNLOCK();
		return NULL;
	}

#ifdef	OBLITERATE
	memset(ADDR(store), '\001', size);
#endif	/* OBLITERATE */

#if	MEM_DEBUG
	store->x.file = file;
	store->x.line = line;
#endif

	g_mem->total += size;
	STATUS("malloc");

	UNLOCK();
	return ADDR(store);
}	/* mem_malloc */

/* ARGUSED */
caddr_t mem_calloc(uint32_t num, size_t size FILE_LINE_ARGS)
{
	mem_node_t *store;
	uint32_t bytes;
	FUN("mem_calloc");

	if (NULL == g_mem) mem_pool();
	LOGS(L_MEM,L_DEBUGX,("mem_calloc(%u,%d)%s\n",
		(unsigned)num, (int)size, AT_FILE_LINE));

	if (0 != LOCK()) {
		LOGS(L_MEM,L_ERROR,("lock failed%s\n",
			AT_FILE_LINE));
		return NULL;
	}

	if (0 == num && 0 == size) {
		LOGS(L_MEM,L_ERROR,("calloc: attempt to allocate 0 items of size 0%s\n",
			AT_FILE_LINE));
#ifdef	ZERO_ERROR
#if	MEM_DEBUG
		if (NULL != file)
			debug();
#endif
		UNLOCK();
		return NULL;
#endif	/* ZERO_ERROR */
	}

	if (0 == num) {
		LOGS(L_MEM,L_ERROR,("calloc: attempt to allocate 0 items of size %d%s\n",
			(int)size, AT_FILE_LINE));
#ifdef	ZERO_ERROR
#if	MEM_DEBUG
		if (NULL != file)
			debug();
#endif
		UNLOCK();
		return NULL;
#endif	/* ZERO_ERROR */
	}

	if (0 == size) {
		LOGS(L_MEM,L_ERROR,("calloc: attempt to allocate %u items of size 0%s\n",
			(unsigned)num, AT_FILE_LINE));
#ifdef	ZERO_ERROR
#if	MEM_DEBUG
		if (NULL != file)
			debug();
#endif
		UNLOCK();
		return NULL;
#endif	/* ZERO_ERROR */
	}

	bytes = num * size;

	store = FIT(bytes);

	if (NULL == store) {
		LOGS(L_MEM,L_ERROR,("calloc: unable to allocate %u bytes%s\n",
			(unsigned)bytes, AT_FILE_LINE));
		debug();
		UNLOCK();
		return NULL;
	}

	memset(ADDR(store), '\000', bytes);
#if	MEM_DEBUG
	store->x.file = file;
	store->x.line = line;
#endif

	g_mem->total += bytes;
	STATUS("calloc");

	UNLOCK();
	return ADDR(store);
}	/* mem_calloc */

/* ARGUSED */
caddr_t mem_realloc(caddr_t ptr, size_t size FILE_LINE_ARGS)
{
	mem_node_t *t;
	mem_node_t *store;
	FUN("mem_realloc");

	if (NULL == g_mem) mem_pool();
	LOGS(L_MEM,L_DEBUGX,("mem_realloc(%p,%d)%s\n",
		ptr, (int)size, AT_FILE_LINE));
	if (NULL == ptr) {
		return mem_malloc(size FILE_LINE_PARMS);
	}

	if (0 != LOCK()) {
		LOGS(L_MEM,L_ERROR,("lock failed%s\n",
			AT_FILE_LINE));
		return NULL;
	}

	t = find(g_mem->allocated, ptr);
	if (NULL == t) {
		LOGS(L_MEM,L_ERROR,("realloc: attempt to realloc unallocated memory (%p)%s\n",
			ptr, AT_FILE_LINE));
		debug();
		UNLOCK();
		return NULL;
	}

	checkbounds(t, "realloc");

	g_mem->total += size - t->x.usize;
	STATUS("realloc");

	if (t->x.rsize >= size) {

		fillbounds(t);

#ifdef	OBLITERATE
		if (t->x.rsize != size) {
			memset(ADDR(t) + t->x.usize, '\001', size - t->x.usize);
		}
#endif	/* OBLITERATE */

		t->x.usize = size;
#if	MEM_DEBUG
		t->x.file = file;
		t->x.line = line;
#endif

		UNLOCK();
		return ADDR(t);
	}

	store = FIT(size);

	if (NULL == store) {
		LOGS(L_MEM,L_ERROR,("realloc: unable to allocate %d bytes%s\n",
			(int)size, AT_FILE_LINE));
		debug();
		return NULL;
	}

	memcpy(ADDR(store), ADDR(t), MIN(t->x.usize, size));

	assert(NULL == find(g_mem->available, ptr));
	assert(t == find(g_mem->allocated, ptr));

	delete(ALLOC, t);
	insert(AVAIL, t);

	assert(NULL == find(g_mem->allocated, ptr));
	/*
	 * collapsing prevents us from checking:
	 * assert(t == find(g_mem->available, ptr));
	 */

#if	MEM_DEBUG
	store->x.file = file;
	store->x.line = line;
#endif

	UNLOCK();
	return ADDR(store);
}	/* mem_realloc */

/* ARGUSED */
char *mem_strdup(const char *src FILE_LINE_ARGS)
{
	caddr_t ptr;
	size_t size;
	FUN("mem_strdup");

	if (NULL == g_mem) mem_pool();
	LOGS(L_MEM,L_DEBUGX,("mem_strdup(%p)%s\n",
		src, AT_FILE_LINE));

	if (NULL == src) {
		return NULL;
	}
	size = strlen(src) + 1;
	ptr = mem_calloc(size, sizeof(char) FILE_LINE_PARMS);
	if (NULL == ptr) {
		LOGS(L_MEM,L_ERROR,("strdup: unable to allocate %d bytes%s\n",
			(int)size, AT_FILE_LINE));
		debug();
		return NULL;
	}
	/* safer to use strncpy, because another process might have changed src */
	strncpy(ptr, src, size);
	*(char *)(ptr + size - 1) = '\0';
	return (char *)ptr;
}	/* mem_strdup */

/* ARGUSED */
char *mem_strndup(const char *src, size_t size FILE_LINE_ARGS)
{
	caddr_t ptr;
	FUN("mem_strndup");

	if (NULL == g_mem) mem_pool();
	LOGS(L_MEM,L_DEBUGX,("mem_strndup(%p,%#x)%s\n",
		src, (int)size, AT_FILE_LINE));

	if (NULL == src) {
		return NULL;
	}
	ptr = mem_calloc(size, sizeof(char) FILE_LINE_PARMS);
	if (NULL == ptr) {
		LOGS(L_MEM,L_ERROR,("strndup: unable to allocate %d bytes%s\n",
			(uint32_t)size, AT_FILE_LINE));
		debug();
		return NULL;
	}
	strncpy(ptr, src, size);
	*(char *)(ptr + size - 1) = '\0';
	return (char *)ptr;
}	/* mem_strndup */

/* ARGUSED */
void mem_free(caddr_t ptr FILE_LINE_ARGS)
{
	mem_node_t *t;
	FUN("mem_free");

	if (NULL == g_mem) mem_pool();
	LOGS(L_MEM,L_DEBUGX,("mem_free(%p)%s\n",
		ptr, AT_FILE_LINE));

#if	NULL_ERROR
	if (NULL == ptr) {
		LOGS(L_MEM,L_ERROR,("free: attempt to free NULL%s\n",
			AT_FILE_LINE));
#if	MEM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		return;
	}
#else
	if (NULL == ptr) {
		return;
	}
#endif

#if	INVALID_ERROR
	if (INVALID_ADDR == ptr) {
		LOGS(L_MEM,L_ERROR,("free: attempt to free INVALID_ADDR%s\n",
			AT_FILE_LINE));
#if	MEM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		return;
	}
#else
	if (INVALID_ADDR == ptr) {
		return;
	}
#endif

	if (0 != LOCK()) {
		LOGS(L_MEM,L_ERROR,("lock failed%s\n",
			AT_FILE_LINE));
		return;
	}
	t = find(g_mem->allocated, ptr);

	if (NULL == t) {
		LOGS(L_MEM,L_ERROR,("free: attempt to free unallocated memory (0x%x)%s\n",
			(uint32_t)ptr, AT_FILE_LINE));
#if	MEM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		UNLOCK();
		return;
	}

	checkbounds(t, "free");

	assert(t == find(g_mem->allocated, ptr));
	assert(NULL == find(g_mem->available, ptr));

	delete(ALLOC, t);
	insert(AVAIL, t);

	assert(NULL == find(g_mem->allocated, ptr));
	/*
	 * collapsing prevents us from checking:
	 * assert(t == find(g_mem->available, ptr));
	 */

#ifdef	OBLITERATE
	memset(ADDR(t), '\002', t->x.usize);
#else
	/* paranoid */
	memset(ADDR(t), '\000', t->x.usize);
#endif	/* OBLITERATE */

	g_mem->total -= t->x.usize;

	*ptr = 0;

	STATUS("free");
	UNLOCK();
}	/* mem_free */

/* ARGUSED */
int mem_valid(caddr_t ptr FILE_LINE_ARGS)
{
	mem_node_t *t;
	FUN("mem_valid");

	if (NULL == g_mem) mem_pool();
	LOGS(L_MEM,L_DEBUGX,("mem_valid(%p)%s\n",
		ptr, AT_FILE_LINE));
	if (0 != LOCK()) {
		LOGS(L_MEM,L_ERROR,("lock failed%s\n",
			AT_FILE_LINE));
		errno = EINVAL;
		return -1;
	}
	if (NULL == ptr) {
		LOGS(L_MEM,L_DEBUGX,("free: attempt to validate NULL%s\n",
			AT_FILE_LINE));
#if	MEM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		UNLOCK();
		errno = EINVAL;
		return -1;
	}
	STATUS("valid");

	t = find(g_mem->allocated, ptr);

	if (NULL == t) {
		LOGS(L_MEM,L_DEBUG,("invalid pointer (%p)%s\n",
			ptr, AT_FILE_LINE));
#if	MEM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		UNLOCK();
		errno = EINVAL;
		return - 1;
	}

	checkbounds(t, "valid");

	UNLOCK();
	return 0;
}	/* mem_valid */

/* ARGUSED */
int mem_stats(mem_pool_stats_t *stats FILE_LINE_ARGS)
{
	size_t seg;
	FUN("mem_stats");

	if (NULL == g_mem) mem_pool();
	LOGS(L_MEM,L_DEBUGX,("mem_stats(%p)%s\n",
		stats, AT_FILE_LINE));

	if (NULL == stats) {
#if	MEM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		errno = EINVAL;
		return -1;
	}
	if (0 != LOCK()) {
		LOGS(L_MEM,L_ERROR,("lock failed%s\n",
			AT_FILE_LINE));
		errno = EINVAL;
		return -1;
	}
	stats->total = 0;
	stats->used = 0;
	stats->free = 0;
	stats->allocated = g_mem->alloc_len;
	stats->available = g_mem->avail_len;
	for (seg = 0; seg < g_mem->pool_cnt; seg++) {
		stats->total += g_mem->max[seg];
		stats->used += g_mem->brk[seg];
		stats->free += g_mem->max[seg] - g_mem->brk[seg];
	}
	UNLOCK();
	return 0;
}

void mem_pool_exit(void)
{
	FUN("mem_pool_exit");
	if (NULL != g_mem) {
		free(g_mem);
		g_mem = NULL;
	}
}

int mem_pool(void)
{
	size_t size;
	FUN("mem_pool");

	size = MEM_POOLSIZE;
	g_mem = calloc(1, sizeof(mem_pool_t) + size);
	g_mem->pool[0] = &g_mem->data[0];
	g_mem->brk[0] = 0;
	g_mem->max[0] = size;
	g_mem->pool_cnt = 1;

	return 0;
}
#else	/* MEM_ALLOC_IMPL */

/* ARGUSED */
caddr_t mem_malloc(size_t size FILE_LINE_ARGS)
{
	return malloc(size);
}

/* ARGUSED */
caddr_t mem_calloc(uint32_t num, size_t size FILE_LINE_ARGS)
{
	return calloc(num, size);
}

/* ARGUSED */
caddr_t mem_realloc(caddr_t ptr, size_t size FILE_LINE_ARGS)
{
	return realloc(ptr, size);
}

/* ARGUSED */
char *mem_strdup(const char *src FILE_LINE_ARGS)
{
	return strdup(src);
}

/* ARGUSED */
char *mem_strndup(const char *src, size_t size FILE_LINE_ARGS)
{
	char *dst = mem_calloc(size, sizeof(char) FILE_LINE_ARGS);
	if (!dst)
		return NULL;
	strncpy(dst, src, size);
	dst[size-1] = '\0';
	return dst;
}

/* ARGUSED */
void mem_free(caddr_t ptr FILE_LINE_ARGS)
{
	free(ptr);
}

/* ARGUSED */
int mem_valid(caddr_t ptr FILE_LINE_ARGS)
{
	if (NULL == ptr)
		return -1;
	return 0;
}

/* ARGUSED */
int mem_stats(mem_pool_stats_t *stats FILE_LINE_ARGS)
{
	errno = ENODEV;
	return -1;
}

void mem_pool_exit(void)
{
}

int mem_pool(void)
{
	return 0;
}

#endif	/* MEM_ALLOC_IMPL */
